package leetcode.editor.cn.q1_300.q200;
//给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 13
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：n = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 10⁹ 
// 
//
// 👍 514 👎 0

/**
 * 思路：
 * 假设 n 是 123 1 的个数为：
 * <p>
 * 个位上的 1 会出现 13 次
 * 十位上的 1 会出现 20 次 （百位 2 次 * 个位 10 次）
 * 百位上的 1 会出现 24 次
 * 一共出现 57 次
 * <p>
 * 222
 * 个位 23
 * 十位 3 * 10
 * 百位 100
 * 一共 153
 * <p>
 * 总结：注意最高位和最低位，其他的都是前面的数 * 后面的位数
 */
public class Q233_NumberOfDigitOne {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countDigitOne(int n) {

            if (n == 0) return 0;

            int num = 0;
            // 从左数的位数
            int index = 1;
            while (true) {
                int cur = n / index % 10;
                int left = n / (index * 10);

                if (left == 0) {
                    /**
                     * 最高位 1 出现的次数
                     * 如果最高位是 1 就是除了最高位之外的数字 +1
                     * eg。123 百位的 1 就会出现 24 次
                     *
                     * 最高位是不是 1 那就是出现 10的最高位位数次幂
                     * eg。223 百位的 1 就会出现 100 次
                     */
                    num += cur == 1 ? (n % index + 1) : index;
                    break;
                } else if (index == 1) {
                    /**
                     * 个位：
                     * 个位上是 0，
                     * eg。120 个位 1 就会出现 120次
                     * 个位上不算 0，
                     * eg。121 个位 1 就会出现 121次
                     */
                    num += cur == 0 ? left : left + 1;
                } else {
                    /**
                     * 除了最高和个位之外，其他位：
                     * 如果是 0，左侧数 * 位数。 eg.1102 十位上的 1 出现了 11 * 10 = 110 次
                     * 如果是 1，左侧数 * 位数 + 右侧数  eg.1120 百位上 1 出现了 1 * 100 + 21 = 121 次
                     * 如果是其他数，(左侧数+1) * 位数 eg. 1234 十位上的 1 出现了 130 次
                     */
                    if (cur == 0) {
                        num += left * index;
                    } else if (cur == 1) {
                        num += left * index + (n % index + 1);
                    } else {
                        num += (left + 1) * index;
                    }
                }

                index *= 10;
            }

            return num;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q233_NumberOfDigitOne().new Solution();
//        System.out.println(solution.countDigitOne(10));
//        System.out.println(solution.countDigitOne(0));
//        System.out.println(solution.countDigitOne(4));
//        System.out.println(solution.countDigitOne(13));
//        System.out.println(solution.countDigitOne(123));
        System.out.println(solution.countDigitOne(1102));
        System.out.println(getNum(1102));
        for (int i = 0; i < 1000; i++) {
            if (solution.countDigitOne(i) != getNum(i)) {
                System.out.println("出错了：" + i);
                System.out.println(solution.countDigitOne(i) + "\t" + getNum(i));
                break;
            }
        }
    }

    private static int getNum(int target) {
        int num = 0;
        for (int i = 0; i <= target; i++) {
            String str = String.valueOf(i);
            if (str.contains("1")) {
//                System.out.println(str);
            }
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '1') {
                    num++;
                }
            }
        }
        return num;
    }
}